package codingforgreat.lchot150;

public class Lc268 {
    public static int missingNumber(int[] arr) {
        // l是盯着的位置
        // 0 ~ L-1有效区
        int L = 0;
        int R = arr.length;
        while (L != R) {
            if (arr[L] == L) {
                L++;
            } else if (arr[L] < L || arr[L] >= R || arr[arr[L]] == arr[L]) { // 垃圾的情况
                swap(arr, L, --R);
            } else {
                swap(arr, L, arr[L]);
            }
        }
        return L;
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
